[파이썬알고리즘인터뷰]#6 문자열 조작(String Manipulation)
🔥 algorithm | February 10, 2021
문자열을 변경하거나 분리하는 등의 여러 과정을 말합니다. 문자열 조작은 코딩 데스트에도 매우 빈번하게 출되며 실무에서도 다양한 분야에 쓰이는 상당히 실용적인 주제입니다.
- 정보 처리 분야: 어떤 키워드로 웹 페이지를 탐색할 때 문자열 처리 애플리케이션을 이용하며, 문자열 처리는 정보 처리에 핵심적인 역할을 합니다.
- 통신 시스템 분야: 데이터 전송에서 문자열 처리는 매우 중요한 역할을 합니다.
- 프로그래밍 시스템 분야: 프로그램은 그 자체가 문자열로 구성되고, 컴파일러나 인터프리터 등은 문자열을 해석하고 처리하여 기계어로 변환하는 역할을 합니다.
유효한 팰린드롬
팰린드롬이란 앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장입니다.
예제1
입력: “A man, a plan, a canal: panama”
출력: true
예제2
입력: “race a car”
출력: false
풀이1
# 전처리
# 대소문자 여부를 구분하지 않으며 영문자, 숫자만을 대상으로 한다는 제약 조건
def isPallindrome(s: str) -> bool:
strs = []
for char in s:
if char.isalnum():
strs.append(char.lower())
# 팰린드롬 여부 판별
while len(strs) > 1:
if strs.pop(0) != strs.pop():
return False
return True
isalnum(): 영문자, 숫자 여부를 판별하는 함수로, 이를 이용해 문자만 추가한다. (특수문자 등 제외함)또한 대소문자를 구별하지 않으므로
lower()로 모두 소문자로 변환
풀이2 - 데크 자료형을 이용한 최적화
import collections
def isPallindrome(s: str) -> bool:
# 자료형 데크로 선언
strs: Deque = collections.deque()
for char in s:
if char.isalnum():
strs.append(char.lower())
# 팰린드롬 여부 판별
while len(strs) > 1:
if strs.popleft() != strs.pop():
return False
return True
print(isPallindrome("A man, a plan, a canal: Panama"))strs: Deque = collections.deque() 자료형을 데크로 선언함
풀이3 - 슬라이싱 사용
import re
def isPallindrome(s: str) -> bool:
s = s.lower()
# 정규식으로 불필요한 문자 필터링
s = re.sub('^[a-z0-9]', '', s)
return s == s[::1] # 슬라이싱
print(isPallindrome("A man, a plan, a canal: Panama"))앞선 isalnum()으로 모든 문자를 일일이 점검한 것과는 다르게 문자열 전체를 영숫자(Alphanumeric)만 걸러내도록 정규식으로 처리했다. 코드가 줄어들었으며 슬라이싱은 내부적으로 C로 구현되어 있어 빠른 속도를 기대할 수 있다.
문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리하다.
문자열 뒤집기
문자열을 뒤집는 함수를 작성하라. 입력 값은 문자 배열이며, 리턴 없이 리스트 내부를 직접 조작하라
투 포인터를 이용한 스왑
전통적인 풀이방식이며, 2개의 포인터를 이용해 범위를 조정해가며 풀이하는 방식이다.
여기서는 범위를 점점 좁혀가며 스왑하는 형태로 풀이할 수 있다.
List = ["h","e","l","l","o"]
def reverseString(s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1파이썬 다운 방식
List = ["h","e","l","l","o"]
def reverseString(s):
s.reverse()
# 또는
# S[:] = S[::-1]로그 파일 재정렬
로그를 재정렬하라. 기준은 다음과 같다.
- 로그의 가장 앞 부분은 식별자다.
- 문자로 구성된 로그가 숫자 로그보다 앞에 온다.
- 식별자는 순서에 영향을 끼치지 않지만, 문자가 동일한 경우 식별자 순으로 한다.
- 숫자 로그는 입력 순서대로 한다.
# 문제 해결 방식
# 문자로 구성된 로그가 숫자 로그보다 이전에 오며, 숫자 로그는 입력 순서대로 둔다.
# > 문자와 숫자를 구분하고 숫자는 나중에 그대로 이어 붙인다.
def reorderLogFiles(logs):
letters, digits = [], []
for log in logs:
# 로그 자체는 숫자 로그도 모두 문자열로 지정되어 있으므로,
# 타입을 확인하면 모두 문자로 출력된다.
# > 따라서 isdigit()을 이용해서 숫자 여부인지를 판별해 구분해준다.
# 앞의 split()[0]은 식별자 이므로 [1]를 숫자인지 문자인지 체크
if log.split()[1].isdigit():
digits.append(log)
else:
letters.append(log)
print(digits, letters)
# 2개의 키를 람다 표현식으로 정렬
# 식별자를 제외한 [1:]을 키로 정렬하고, 동일한 경우 후순위로 식별자[0]를 기준으로 정렬
letters.sort(key=lambda x: (x.split()[1:], x.split()[0]))
return letters + digits
print(reorderLogFiles(["dig1 8 1 5 1", "let1 art can", "dig2 3 6", "let2 own kit dig", "let3 art zero"]))isdigit() : 숫자인지 판별해준다.
람다 표현식 예시
# s를 뒤의 알파벳 기준으로 정렬하고, 알파벳이 같다면 앞의 숫자를 기준으로 정렬하는 것으로 함
s = ['1 A', '1 B', '2 A', '4 C']
# 1번
s.sort()
print(s)
# 결과: ['1 A', '1 B', '2 A', '4 C']
# 우리가 원하던 결과가 아니다. 앞의 숫자를 기준으로 정렬되었음
# 2번
s = ['1 A', '1 B', '2 A', '4 C']
s.sort(key=lambda x : (x.split()[1], x.split()[0]))
print(s)
# 결과: ['1 A', '2 A', '1 B', '4 C']
# 알파벳을 기준으로 우선 정렬 후, 알파벳이 같다면 앞의 숫자를 기준으로 잘 정렬되었다.
# 3번 예시
def func(s):
return s.split()[1], s.split()[0]
s.sort(key=func)
print(s)
# 동일한 결과가 출력된다.위로 올라가기💨
